package com.desheng.bigdata.ds.link;

/**
 * @Description 快慢指针解决环入口的问题。
 *      就是说一个链表中，通过有两个指针，一个指针移动的速度快，另外一个移动的速度慢，
 *      通常快指针移动的速度是慢指针的2倍.
 *      使用快慢指针来检测一个链表是否有环。因为如果没有环的话，快慢指针永远不可能相遇的，而如果有环，快指针就会
 *      在一定时间之后追上慢指针。
 *      就比如在操场上跑步，一个人跑的快，一个人跑的慢，快的人是可以追上跑的慢的人的。
 *
 *      当快慢指针相遇的时候，此时定义一个临时指针，速度和慢指针一致，向后移动，当临时指针和慢指针相遇，则就是环的入口，
 *      证明需要数论的相关知识，这里略去。
 *
 * @Author deshenglijun
 * @Date 2020/5/12 21:41
 * @Version 1.0
 */
public class FastAndSlowPointer2CircleEntrance {
    public static void main(String[] args) {
        Node<String>[] nodes = new Node[10];
        for(int i = 0; i < nodes.length; i++) {
            nodes[i] = new Node<String>(null, i + "" + i);
        }
        //组成一个链表
        for(int i = 0; i < nodes.length - 1;) {
            nodes[i].next = nodes[++i];
        }
        nodes[nodes.length - 1].next = nodes[3];

        String entrance = getEntrance(nodes[0]);
        System.out.println("entrance: " + entrance);
    }

    /**
     * 通过快慢指针来判断链表是否有环
     * @param node
     * @return
     */
    private static <E> E getEntrance(Node<E> node) {
        Node<E> fast = node;
        Node<E> slow = node;
        Node<E> entrance = null;
        while(fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;

            if(fast == slow) {
                entrance = node;
                continue;
            }
            if(entrance != null) {
                entrance = entrance.next;
                if(slow == entrance) {
                    return entrance.data;
                }
            }
        }
        return entrance == null ? null : entrance.data;
    }


    static class Node<E> {
        E data;
        Node<E> next;

        public Node(Node<E> next, E data) {
            this.data = data;
            this.next = next;
        }
    }
}
